package offer

/*
时间复杂度:O(N^2)
空间复杂度:O(N^2)

二维前缀和(扩充边界,避免考虑边界情况): 在边界情况处理比较麻烦的时,可以使用扩充边界的方法,即长度和宽度各扩充一个单位
preSum[i+1][j+1] = matrix[i][j] + preSum[i+1][j] + preSum[i][j+1] - preSum[i][j]
*/

type NumMatrix struct {
	pre [][]int
}

func Constructor(matrix [][]int) NumMatrix {
	m, n := len(matrix), len(matrix[0])
	preSum := make([][]int, m+1)
	preSum[0] = make([]int, n+1)
	for i, row := range matrix {
		preSum[i+1] = make([]int, n+1)
		for j, _ := range row {
			preSum[i+1][j+1] = matrix[i][j] + preSum[i+1][j] + preSum[i][j+1] - preSum[i][j]
		}
	}
	return NumMatrix{pre: preSum}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	return this.pre[row2+1][col2+1] - this.pre[row2+1][col1] - this.pre[row1][col2+1] + this.pre[row1][col1]
}

/*
时间复杂度:O(N^2)
空间复杂度:O(1) 数组原地存储

f2:二维前缀和

求二维前缀和类比于求路径和的dp二维过程, 先处理上边界和左边界,然后
	matrix[i][j] += matrix[i-1][j] + matrix[i][j-1] - matrix[i-1][j-1]
*/

type NumMatrix2 struct {
	pre [][]int
}

func Constructor2(matrix [][]int) NumMatrix {
	m, n := len(matrix), len(matrix[0])
	for i := 1; i < m; i++ {
		matrix[i][0] += matrix[i-1][0]
	}
	for j := 1; j < n; j++ {
		matrix[0][j] += matrix[0][j-1]
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			matrix[i][j] += matrix[i-1][j] + matrix[i][j-1] - matrix[i-1][j-1]
		}
	}
	return NumMatrix{pre: matrix}
}

func (this *NumMatrix) SumRegion2(row1 int, col1 int, row2 int, col2 int) int {
	leftRow, leftCol := row2, col1-1
	upRow, upCol := row1-1, col2

	ans := this.pre[row2][col2]
	var flag bool
	if leftRow >= 0 && leftCol >= 0 {
		ans -= this.pre[leftRow][leftCol]
	} else {
		flag = true
	}
	if upRow >= 0 && upCol >= 0 {
		ans -= this.pre[upRow][upCol]
	} else {
		flag = true
	}

	if !flag {
		ans += this.pre[row1-1][col1-1]
	}
	return ans
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * obj := Constructor(matrix);
 * param_1 := obj.SumRegion(row1,col1,row2,col2);
 */